package com.zjsru.plan2023.oneday;

/**
 * @Author: cookLee
 * @Date: 2023-12-13
 * 字典序最小回文串
 */
public class MakeSmallestPalindrome {
    /**
     * 主
     * \
     * 输入：s = "egcfe"
     * 输出："efcfe"
     * 解释：将 "egcfe" 变成回文字符串的最小操作次数为 1 ，修改 1 次得到的字典序最小回文字符串是 "efcfe"，只需将 'g' 改为 'f' 。
     * \
     * 输入：s = "abcd"
     * 输出："abba"
     * 解释：将 "abcd" 变成回文字符串的最小操作次数为 2 ，修改 2 次得到的字典序最小回文字符串是 "abba" 。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MakeSmallestPalindrome makeSmallestPalindrome = new MakeSmallestPalindrome();
        String s = "egcfe";
        System.out.println(makeSmallestPalindrome.makeSmallestPalindrome(s));
    }

    /**
     * 做最小回文
     * 双指针
     * @param s s
     * @return {@link String}
     */
    public String makeSmallestPalindrome(String s) {
        char[] chars = s.toCharArray();
        int left = 0, right = s.length() - 1;
        while (left < right) {
            char leftChar = chars[left];
            char rightChar = chars[right];
            if (leftChar != rightChar) {
                //两端指针同步最小值
                chars[left] = (char) Math.min(leftChar, rightChar);
                chars[right] = (char) Math.min(leftChar, rightChar);
            }
            //修改两个指针
            left++;
            right--;
        }
        return new String(chars);
    }


}
